package com.cyz.springdemo.Controller;

import com.cyz.springdemo.model.test.ListNode;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.bind.annotation.RestController;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @program: springdemo
 * @description: 算法题
 * @author: wangjie
 * @create: 2019-08-05 09:30
 **/
@RestController
@RequestMapping(value = "/algorithm")
public class AlgorithmController {

    /**
     * 题目描述：
     * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。
     * 数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。
     * 请找出数组中任意一个重复的数字。
     * 例：
     * Input:
     * {2, 3, 1, 0, 2, 5}
     * Output:
     * 2
     */
    private static int nums[] = {2, 3, 1, 0, 2, 5};

    @RequestMapping(value = "/duplicate",method = RequestMethod.GET)
    public boolean duplicate(int length, int[] duplicate){

        if (nums == null || length < 0){
            return false;
        }
        for (int i=0;i<length;i++){
            while (nums[i] != i){
                if (nums[i] == nums[nums[i]]){
                    duplicate[0] = nums[i];
                    return true;
                }
                swap(nums,i,nums[i]);
            }
        }

        return false;
    }

    public void swap(int[] nums, int i,int j){
        int t = nums[i];
        nums[j] = nums[i];
        nums[i] = t;
    }


    /**
     * 题目描述：
     * 将一个字符串中的空格替换成 "%20"。
     * 例：
     * Input:
     * "A B"
     * Output:
     * "A%20B"
     *
     */
    @RequestMapping(value = "/replace" , method = RequestMethod.GET)
    public String replaceSpace(String s){
        StringBuffer str = new StringBuffer(s);
        if (str.length() <= 0){
            return "";
        }
        int p1 = str.length() -1;   //p1的位置
        for (int i=0;i<=p1;i++){
            //如果有空格则在字符串后面添加两个位置
            if (str.charAt(i) == ' '){
                str.append("  ");
            }
        }

        int p2 = str.length() - 1;  //p2的位置
        while(p1 >= 0 && p2>p1){
            char c = str.charAt(p1--);
            if (c == ' '){
                str.setCharAt(p2--,'0');
                str.setCharAt(p2--,'2');
                str.setCharAt(p2--,'%');
            }else {
                str.setCharAt(p2--,c);
            }
        }
        return str.toString();
    }

    /**
     * 题目描述：
     * 从尾到头反过来打印出每个结点的值。
     * input：
     * 1->2->3
     * output:
     * 3->2->1
     * 解题思路：用栈，先进后出
     */
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode){

        Stack<Integer> stack = new Stack<>();
        if (listNode != null){
            stack.add(listNode.val);
            listNode = listNode.next;
        }

        ArrayList<Integer> ret = new ArrayList<>();
        while (!stack.empty()){
            ret.add(stack.pop());
        }
        return ret;
    }

    /**
     * 题目描述：
     * 用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。
     * 解题思路：
     * inStack栈用来处理入栈push的操作，outStack栈用来处理出栈pop的操作。一个元素进入in栈之后，顺序被反转，而当要出栈时，元素被放入到
     * out栈中，这时候顺序又会被反转，此时出栈的元素顺序就跟原先入栈的顺序一致，先进先出，行程队列顺序。
     */

    Stack<Integer> inStack = new Stack<>();
    Stack<Integer> outStack = new Stack<>();

    public void push(int node){
        inStack.push(node);
    }

    public int pop() throws Exception {

        if (!outStack.empty()){
            while (!inStack.empty()){
                outStack.push(inStack.pop());
            }
        }

        if (outStack.empty()){
            throw new Exception("quene is empty");
        }

        return outStack.pop();
    }
}
